package Solution101_200.problem117.II116;

import common.Node;

import java.util.ArrayList;
import java.util.List;

/**
 * @program Leetcode
 * @description:
 * @author: lishangsheng
 * @create: 2019/07/17 18:19
 */
public class Solution {
    public Node connect(Node root) {
        //自顶向上递归
        if (root == null) return null;
        List<Node> nextLevel = new ArrayList<>();
        nextLevel.add(root);
        connectList(nextLevel);
        return root;
    }

    private void connectList(List<Node> levelNode) {
        List<Node> nextLevel = new ArrayList<>();
        for (int i = 0; i < levelNode.size(); i++) {

            Node node = levelNode.get(i);
            if (i != levelNode.size()-1) {
                node.next = levelNode.get(i + 1);
            } else {
                node.next = null;
            }
            if (node.left != null) {
                nextLevel.add(node.left);
            }
            if (node.right != null) {
                nextLevel.add(node.right);
            }
        }


        if (nextLevel.size() == 0) {
            return;
        }
        connectList(nextLevel);

    }
}
